Saltar para o conteúdo

Gramática livre do contexto generalizada

Origem: Wikipédia, a enciclopédia livre.


Gramática Livre do Contexto Generalizada (GLCG) é um formalismo de gramática que expande-se sobre as Gramáticas Livres de Contexto por adicionar composições de funções potencialmente não livres de contexto para re-escrever as regras.[1] Gramática de Cabeça (e seus equivalentes fracos) é uma instância de uma GLCG que é conhecida por ser especialmente adepta em manusear uma grande variedade de propriedades não livres do contexto da linguagem natural.

Uma GLCG consiste de dois componentes: um conjunto de funções de composição que combina tuplas de cadeias e um conjunto de regras de re-escrita. As funções de composição todas tem a forma , onde é ou uma tupla de cadeias ou algum uso de uma (potencialmente diferente) função de composição que se reduz a uma tupla de cadeias. Regras de re-escrita se parecem com , onde , , ... são tuplas de cadeias ou símbolos não terminais.

A semântica de reescrita de uma GLCG é relativamente direta. Uma ocorrência de um símbolo não terminal é re-escrito usando as regras de re-escrita assim como numa GLC, eventualmente gerando apenas composições (funções de composições aplicadas a tuplas de cadeias ou outras composições). As funções são então aplicadas, reduzindo sucessivamente as tuplas a uma única tupla.

A simples tradução de uma GLC para uma GLCG pode ser feita da seguinte maneira. Dada a gramática em (1), que gera a linguagem de palíndromes , onde é a cadeira reversa de , nós podemos definir a função de composição "conc" como em (2a) e as regras de re-escrita como em (2b)

A simple translation of a context-free grammar into a GCFG can be performed in the following fashion. Given the grammar in (1), which generates the palindrome language , where is the string reverse of , we can define the composition function conc as in (2a) and the rewrite rules as in (2b).

A produção livre d contexto de "abbbba" é:

S

aSa

abSba

abbSbba

abbbba

E a produção correspondente via GLCG é

Sistemas Lineares de Re-escrita Livre do Contexto (SLRLCs)

[editar | editar código-fonte]

Weir (1988)[1] descreve duas propriedades das funções de composição, linearidade e regularidade. Uma função definida como é linear sse cada variável aparece no máximo uma vez em cada lado do "=", fazendo linear mas não. Uma função definida como é regular se o lado esquero e o direito têm exatamente as mesmas variáveis, fazendo regular mas ou não.

Uma gramática em que todas as funções de composição são lineares e regulares é chamada um Sistema Linear de Re-escrita Livre do Contexto (SLRLC), um subconjunto das GLCG com estritamente menos poder computacional que as GGLC como um todo, que é fracamente equivalente a uma Gramática contígua de árvore multicomponente. Gramática de Cabeça é um exemplo de um SLRLC que é estritamente menos poderoso computacionalmente do que a classe dos SLRLC como um todo.

  1. a b Weir, David H. 1988. Characterizing mildly context-sensitive grammar formalisms. Dissertation, U Penn.